#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef char BIT;

const char *bitap_search(const char *text, const char *pattern)
{
    const char *result = NULL;
    int m = strlen(pattern);
    BIT *R;
    int i, k;

    if (pattern[0] == '\0') return text;

    /* Initialize the bit array R */
    R = malloc((m+1) * sizeof *R);
    for (k=1; k <= m; ++k)
      R[k] = 0;
    R[0] = 1;

    for (i=0; text[i] != '\0'; ++i) {
        /* Update the bit array */
        for (k=m; k >= 1; --k)
          R[k] = R[k-1] && (text[i] == pattern[k-1]);

        if (R[m]) {
            result = (text+i - m) + 1;
            break;
        }
    }

    free(R);
    return result;
}


const char *bitap_bitwise_search(const char *text, const char *pattern)
{
    int m = strlen(pattern);
    unsigned long R;
    unsigned long pattern_mask[CHAR_MAX+1];
    int i;

    if (pattern[0] == '\0') return text;
    if (m > 31) return "The pattern is too long!";
 
    /* Initialize the bit array R */
    R = ~1;

    /* Initialize the pattern bitmasks */
    for (i=0; i <= CHAR_MAX; ++i)
      pattern_mask[i] = ~0;
    for (i=0; i < m; ++i)
      pattern_mask[pattern[i]] &= ~(1UL << i);

    for (i=0; text[i] != '\0'; ++i) {
        /* Update the bit array */
        R |= pattern_mask[text[i]];
        R <<= 1;

        if (0 == (R & (1UL << m)))
          return (text+i - m) + 1;
    }

    return NULL;
}
